﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
#include<cmath>
#include<iostream>
#include<stdlib.h>
#include<assert.h>
using namespace std;
//堆串
//typedef struct
//{
//	char* string;
//	int length;
//}HString;
//
//void Init_String(HString* S)
//{
//	S->length = 0;
//	S->string = NULL;
//}
//void Assign_String(HString* S, const char p[])
//{ 
//	if (S->string != NULL)
//	{
//		free(S->string);
//	}
//	int len = 0;
//	for (int i = 0; p[i] != '\0'; i++)
//	{
//		len++;
//	}
//	S->string = (char*)malloc(sizeof(char) * len);
//	assert(S->string);
//	for (int i = 0; i < len; i++)
//	{
//		S->string[i] = p[i];
//	}
//	S->length = len;
//}
//void Print_String(HString* S)
//{
//	for (int i = 0; i < S->length; i++)
//	{
//		cout << S->string[i];
//	}
//	cout << endl;		
//}
//
//int main()
//{
//	HString S;
//	Init_String(&S);
//	Assign_String(&S, "abcd");
//	Print_String(&S);
//	return 0;;
//}
//----------------------------------------
//整数去重(不要求排序)
//int main()
//{
//	int arr[5010];
//	int brr[5010];
//	int n;
//	cin >> n;
//	for (int i = 0; i < n; i++)
//	{
//		cin >> arr[i];
//		brr[arr[i]] = 1;
//	}
//	for (int i = 0; i < n; i++)
//	{
//		if (brr[arr[i]] != 0)
//		{
//			cout << arr[i] << " ";
//			brr[arr[i]] = 0;
//	    }
//	}
//	return 0;
//}
//----------------------------------
/*有一个有序数字序列，从小到大排序，将一个新输入的数插入到序列中，
保证插入新数后，序列仍然是升序。*/
//int main()
//{
//	int arr[5010];
//	int n;
//	cin >> n;
//	for (int i = 0; i < n; i++)
//	{
//		cin >> arr[i];
//	}
//	int k = 0;
//	cin >> k;
//	for (int i = 0; i < n+1; i++)
//	{
//		if (arr[i] > k)
//		{
//			for (int j = n; j >= i; j--)
//			{
//				arr[j] = arr[j - 1];
//			}
//		}
//		arr[i] = k;
//	}
//	for (int i = 0; i < n + 1; i++)
//	{
//		cout << arr[i] << " ";
//	}
//	return 0;
//}
//--------------------------------
//int main()
//{
//	int n;
//	cin >> n;
//	int arr[5010];
//	for (int i = 0; i < n; i++)
//	{
//		cin >> arr[i];
//	}
//	int k = 0;
//	cin >> k;
//	arr[n] = k;
//	for (int i = 0; i < n ; i++)
//	{
//		for (int j = 0; j < n - i; j++)
//		{
//			if (arr[j] > arr[j + 1])
//			{
//				int temp = arr[j];
//				arr[j] = arr[j + 1];
//				arr[j + 1] = temp;
//			}
//		}
//	}
//	for (int i = 0; i < n + 1; i++)
//	{
//		cout << arr[i] << " ";
//	}
//	return 0;
//}
//----------------------------------------------
//打印质数表
//int main()
//{
//	int n = 0;
//	cin >> n;
//	int flag = 1;
//	for (int i = 2; i <= n; i++)
//	{
//		flag = 1;
//		for (int j = 2; j<=sqrt(i); j++)
//		{
//			if (i % j == 0)
//			{
//				flag = 0;
//			}
//		}
//		if (flag == 1)
//		{
//			cout << i << " ";
//		}
//	}
//	return 0;
//}
//------------------------------------
//素数分布
//int main()
//{
//	int T;
//	cin >> T;
//	while (T--)
//	{
//		int n;
//		cin >> n;
//		int count = 0;
//		int flag = 1;
//		for (int i = 2; i <= n; i++)
//		{
//			flag = 1;
//			for (int j = 2; j <= sqrt(i); j++)
//			{
//				if (i % j == 0)
//				{
//					flag = 0;
//				}
//			}
//			if (flag == 1)
//			{
//				count++;
//			}
//		}
//		cout << count << endl;
//	}
//	return 0;
//}
//--------------------------------------
//有序序列的合并
//int arr[5010];
//int main()
//{
//	int m, n;
//	cin >> m >> n;
//	for (int i = 0; i < m; i++)
//	{
//		cin >> arr[i];
//	}
//	for (int j = 0; j < n; j++)
//	{
//		cin >> arr[m+j];
//	}
//	for (int i = 0; i < m + n -1; i++)
//	{
//		for (int j = 0; j < m + n -1 - i; j++)
//		{
//			if (arr[j] > arr[j + 1])
//			{
//				int temp = arr[j];
//				arr[j] = arr[j + 1];
//				arr[j + 1] = temp;
//			}
//		}
//	}
//	for (int i = 0; i < m + n; i++)
//	{
//		cout << arr[i] << " ";
//	}
//	return 0;
//}
//--------------------------------------
//杨辉三角
//int main()
//{
//	long long arr[50][50] ;
//	int n;
//	cin >> n;
//	for (int i = 0; i < n; i++)
//	{
//		arr[i][0] = 1;
//		arr[i][i] = 1;
//	}
//	for (int i = 2; i < n; i++)
//	{
//		for (int j = 1; j < i; j++)
//		{
//			arr[i][j] = arr[i - 1][j] + arr[i - 1][j - 1];
//		}
//	}
//	for (int i = 0; i < n; i++)
//	{
//		for (int j = 0; j <= i; j++)
//		{
//			cout << arr[i][j] << " ";
//		}
//		cout << endl;
//	}
//	return 0;
//}
//------------------------------------------
//维修广场
//int main()
//{
//	int i, j;
//	int m, n, a;
//	cin >> m >> n >> a;
//	int sum1=0, sum2=0;
//	for (i = 0; sum1 < m; i++)
//	{
//		sum1 += a;
//	}
//	for (j = 0; sum2 < n; j++)
//	{
//		sum2 += a;
//	}
//	cout << i * j;
//	return 0;
//}
//--------------------------------------
//比较月亮大小

//int main()
//{
//	int n = 0;
//	cin >> n;
//	int arr[50];
//	int flag = 1;
//	if (n == 1)
//	{
//		cout << "-1" << endl;
//		return 0;
//	}
//	for (int i = 0; i < n; i++)
//	{
//		cin >> arr[i];
//	}
//	for (int i = 0; i < n - 1; i++)
//	{
//		int j = i + 1;
//		if (arr[i] > arr[j])
//		{
//			flag = 0;
//		}
//	}
//	if (flag == 1)
//	{
//		cout << "UP" << endl;
//	}
//	else
//	{
//		cout << "DOWN" << endl;
//	}
//	return 0;
//}
//-------------------------------------
//比月亮
//int arr[500];
//int main()
//{
//	int n;
//	cin >> n;
//	for (int i = 1; i <= n; i++)
//	{
//		cin >> arr[i];
//	}
//	if (arr[n] == 15)
//	{
//		cout << "DOWN" << endl;
//	}
//	else if (arr[n] == 0)
//	{
//		cout << "UP" << endl;
//	}
//	else
//	{
//		if (n == 1)
//		{
//			cout << -1 << endl;
//		}
//		else
//		{
//			if (arr[n] > arr[n-1])
//			{
//				cout << "UP" << endl;
//			}
//			else
//			{
//				cout << "DOWN" << endl;
//			}
//		}
//	}
//	return 0;
//}
//-----------------------------------------
//校门外的树
/*
输入:500 3
     150 300
     100 200
     470 471
输出：298   */
//int arr[5000];
//int main()
//{
//    int l, m;
//    cin >> l >> m;
//    while (m--)
//    {
//        int kaishi, jieshu;
//        cin >> kaishi >> jieshu;
//        for (int i = kaishi; i <= jieshu; i++)
//        {
//            arr[i] = 1;
//        }
//    }
//    int count = 0;
//    for (int i = 0; i <=l; i++)
//    {
//        if (arr[i] == 0)
//        {
//            count++;
//        }
//    }
//    cout << count << endl;
//}
//-------------------------------------------
//扫雷
/*输入：
4 4
....
..**
*.*.
.*.*
输出：
0122
13**
*4*4
2*3*
*/
//char arr[1010][1010];
//char brr[1010][1010];
//int main()
//{
//    int n = 0;
//    cin >> n;
//    getchar();
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            cin >> arr[i][j];
//        }
//        getchar();
//    }
//    int k = 0;
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < n; j++)
//        {
//            if (arr[i][j] == '*')
//            {
//                brr[i][j] = '*';
//            }
//            else
//            {
//                brr[i][j] = '0';
//                if(arr[i][j])
//            }
//        }
//    }
//    return 0;
//}
//-------------------------------------
//给你n∗m的二维网格，求2∗2的方格的个数，方框里面的字符可以构成'face'
//char arr[55][55];
//int main()
//{
//    int n, m;
//    cin >> n >> m;
//    for (int i = 0; i < n; i++)
//    {
//        getchar();
//        for (int j = 0; j < m; j++)
//        {
//            cin >> arr[i][j];
//        }
//    }
//    int count = 0;
//    for (int i = 0; i < n; i++)
//    {
//        for (int j = 0; j < m; j++)
//        {
//            if (arr[i][j] + arr[i + 1][j] + arr[i][j + 1] + arr[i + 1][j + 1] == 'f' + 'a' + 'c' + 'e')
//            {
//                count++;
//            }
//        }
//    }
//    cout << count << endl;
//    return 0;
//}
//-------------------------------------------
//int main()
//{
//    int arr[50];
//    int n;
//    cin >> n;
//    for (int i = 0; i < n; i++)
//    {
//        cin >> arr[i];
//    }
//    int k = arr[n-1];
//    for(int i=n-1;i>0;i--)
//    {
//        arr[i] = arr[i - 1];
//    }
//    arr[0] = k;
//    for (int i = 0; i < n; i++)
//    {
//        cout << arr[i] << " ";
//    }
//    return 0;
//}
//-------------------------------
//设计一个算法，通过一趟遍历在单链表中确定值最大的结点
//Elemtype MAX(Link head)
//{
//    if (head == NULL || head->next = NULL)
//    {
//        return NULL;
//    }
//    int max = head->data;
//    Link p = head->next;
//    while (p)
//    {
//        if (p->data > max)
//        {
//            max = p->data;
//        }
//        p = p->next;
//    }
//    return max;
//}
//-----------------------------------------------
//设计一个算法，通过遍历一趟，将链表中所有结点的链接方向逆转，仍利用原表的存储空间。
//void Inverse(Link head)
//{
//    Link p = head->next;
//    head->next = NULL;
//    while (p)
//    {
//        Link q = p->next;
//        p->next = head->next;
//        head = p;
//        p = q;
//    }
//}
//---------------------------------------
//回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不是回文。
//试写一个算法判定给定的字符向量是否为回文。(提示：将一半字符入栈)
//#define Elemtype char
//#define MAX_SIZE 100
//typedef struct Stack
//{
//    Elemtype base[MAX_SIZE];
//    int top;
//}Stack;
//bool Is_huiwen(char* p)
//{
//    Stack S;
//    Init(&S);
//    int i = 0;
//    int len = strlen(p);
//    char temp;
//    for (i = 0; i < len / 2; i++)
//    {
//        Push(&S, p[i]);
//    }
//    while (!EmptyStack(&S))
//    {
//        temp = Pop(&S);
//        if (temp != p[i])
//        {
//            return false;
//        }
//        else
//        {
//            i++;
//        }
//    }
//    return true;
//}
//--------------------------------------
